package com.ken.algorithms.linkedList;

import java.util.Scanner;
import java.util.Stack;

/**
 *  CD111. 判断一个链表是否为回文结构
 * 【题目链接】：https://www.nowcoder.com/practice/4b13dff86de64f84ac284e31067b86e2
 *  NowCoder：CD111. 判断一个链表是否为回文结构
 *【题目描述】：
 * 给定一个链表，请判断该链表是否为回文结构。
 * 输入描述:
 * @author 程序员ken
 * @date 2021/5/17 0017 下午 17:24
 */
public class MainCD111_01 {


    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); // 链表长度

//        // 构造链表
//        ListNode head = new ListNode(sc.nextInt()); // 第一个节点
//        ListNode p = head; // 工作指针
//        for (int i = 1; i < n; i ++) {
//            p.next = new ListNode(sc.nextInt());
//            p = p.next;
//        }
//        System.out.println(isPalindrome(n,head));

        //修改单链表 使之添加元素更为直观
        SingleLinkedList<Integer> list = new SingleLinkedList<Integer>();
        for (int i = 0; i < n; i ++) {
            list.add(sc.nextInt());
        }
        System.out.println(isPalindrome(n,list));

    }

    private static boolean isPalindrome(int len, SingleLinkedList<Integer> list) {
        Stack<Integer> stack = new Stack<Integer>();
        int mid = len/2;
        boolean  promise = len%2==0;
        boolean flag  = true;

        ListNode<Integer> p = list.first;// 第一个节点
        int i =0;
        //int len = 0; // 链表长度

        if(len==1){
            return false;
        }

        while (p!=null){
            //一半压入栈 个数为奇数 中间数 不存取
            if(i<mid){
                stack.push(p.item);
            }
            // 个数为奇数 中间数 不存取
            else if(i>mid || (i>=mid && promise)){
                if(!stack.isEmpty() && stack.pop()==p.item){
                    flag =true;
                }else{
                    flag =false;
                }
            }
            p = p.next;// 下个节点指针指向上个节点
            i++;
        }
        return flag;
    }

    /*private static boolean isPalindrome(int len, ListNode head) {

        Stack<Integer> stack = new Stack<Integer>();
        int mid = len/2;
        boolean  promise = len%2==0;
        boolean flag  =true;

        ListNode p = head;// 第一个节点
        int i =0;
        //int len = 0; // 链表长度


        while (p!=null){
            //一半压入栈 个数为奇数 中间数 不存取
            if(i<mid){
                stack.push(p.val);
            }
            // 个数为奇数 中间数 不存取
            else if(i>mid || (i>=mid && promise)){
                if(!stack.isEmpty() && stack.pop()==p.val){
                    flag =true;
                }else{
                    flag =false;
                }
            }
            p = p.next;// 下个节点指针指向上个节点
            i++;
        }
        return flag;

    }*/


    //单链表
    public static class SingleLinkedList<E> {
        transient ListNode<E> first; // 头部节点
        transient ListNode<E> curNode;//当前操作节点
        private  int size;

        //添加元素
        public void add(E e){
            ListNode node = new ListNode(e);
            if(first==null){
                this.first = node;
                this.curNode = node;//一开始就指向这里
            }else{
                ListNode point = this.curNode;//工作指针
                point.next = new ListNode(e);
                this.curNode = point.next;
            }
            size++;
        }


        public int size(){
           return this.size;
        }

    }

    // 定义单链表结构
    public static class ListNode<E> extends SingleLinkedList<Integer> {
        private E item;
        private ListNode<E> next;

        public ListNode(E e) {
            this.item = e;
        }
    }



}
